{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game VI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #game-theory #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #博弈 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stoneGameVI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 VI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 轮流玩一个游戏，Alice 先手。</p>\n",
    "\n",
    "<p>一堆石子里总共有 <code>n</code> 个石子，轮到某个玩家时，他可以 <strong>移出</strong> 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 <strong>不一样的的评判标准</strong> 。双方都知道对方的评判标准。</p>\n",
    "\n",
    "<p>给你两个长度为 <code>n</code> 的整数数组 <code>aliceValues</code> 和 <code>bobValues</code> 。<code>aliceValues[i]</code> 和 <code>bobValues[i]</code> 分别表示 Alice 和 Bob 认为第 <code>i</code> 个石子的价值。</p>\n",
    "\n",
    "<p>所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 <b>最优策略</b> 进行游戏。</p>\n",
    "\n",
    "<p>请你推断游戏的结果，用如下的方式表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 Alice 赢，返回 <code>1</code> 。</li>\n",
    "\t<li>如果 Bob 赢，返回 <code>-1</code> 。</li>\n",
    "\t<li>如果游戏平局，返回 <code>0</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>aliceValues = [1,3], bobValues = [2,1]\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>\n",
    "如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。\n",
    "Bob 只能选择石子 0 ，得到 2 分。\n",
    "Alice 获胜。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>aliceValues = [1,2], bobValues = [3,1]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。\n",
    "打平。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>aliceValues = [2,4,3], bobValues = [1,6,7]\n",
    "<b>输出：</b>-1\n",
    "<strong>解释：</strong>\n",
    "不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。\n",
    "比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。\n",
    "Bob 会获胜。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == aliceValues.length == bobValues.length</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= aliceValues[i], bobValues[i] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-vi](https://leetcode.cn/problems/stone-game-vi/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-vi](https://leetcode.cn/problems/stone-game-vi/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3]\\n[2,1]', '[1,2]\\n[3,1]', '[2,4,3]\\n[1,6,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n=len(aliceValues)\n",
    "        a=[0]*n\n",
    "        alice=0\n",
    "        bobva=0\n",
    "        for i in range(n):\n",
    "            a[i]=aliceValues[i]+bobValues[i]\n",
    "        a.sort(reverse=True)\n",
    "        alice=sum(a[::2])\n",
    "        bobva=sum(bobValues)\n",
    "        if alice>bobva:\n",
    "            return 1\n",
    "        elif alice<bobva:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n=len(aliceValues)\n",
    "        a=[0]*n\n",
    "        alice=0\n",
    "        bobva=0\n",
    "        for i in range(n):\n",
    "            a[i]=aliceValues[i]+bobValues[i]\n",
    "        a.sort(reverse=True)\n",
    "        alice=sum(a[::2])\n",
    "        bobva=sum(bobValues)\n",
    "        if alice>bobva:\n",
    "            return 1\n",
    "        elif alice<bobva:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        totalValues = [(a+b) for a,b in zip(aliceValues, bobValues)]\n",
    "        totalValues.sort(reverse=True)\n",
    "        # 所有Alice能拿到的石头的总价值，其中每个都多拿了Bob的对应石子,再减去本来就是Bob拿的石子，正好是Bob的所有石子\n",
    "        ans = sum(totalValues[::2]) - sum(bobValues)\n",
    "        if ans > 0:\n",
    "            return 1\n",
    "        elif ans < 0:\n",
    "            return -1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        total_values = [(a+b) for a,b in zip(aliceValues,bobValues)]\n",
    "        total_values.sort(reverse = True)\n",
    "        ans = sum(total_values[::2]) - sum(bobValues)\n",
    "        if ans > 0:\n",
    "            return 1\n",
    "        elif ans == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        # 记录两个值和并且降序\n",
    "        totalValue = [(a + b) for a, b in zip(aliceValues, bobValues)]\n",
    "        totalValue.sort(reverse=True)\n",
    "        ans = sum(totalValue[::2]) - sum(bobValues)\n",
    "        if ans > 0:\n",
    "            return 1\n",
    "        elif ans == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        lst=[(a+b) for a,b in zip(aliceValues,bobValues)]\n",
    "        lst.sort(reverse=True)\n",
    "        ans=sum(lst[::2])-sum(bobValues)\n",
    "        if ans>0:\n",
    "            return 1\n",
    "        elif ans==0:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        nums = [x+y for x,y in zip(aliceValues,bobValues)]\n",
    "        nums.sort(reverse=True)\n",
    "        ans = sum(nums[::2]) - sum(bobValues)\n",
    "        if ans > 0:\n",
    "            return 1\n",
    "        elif ans < 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        totalValues = [(a+b) for a,b in zip(aliceValues, bobValues)]\n",
    "        totalValues.sort(reverse=True)\n",
    "        # 所有Alice能拿到的石头的总价值，其中每个都多拿了Bob的对应石子,再减去本来就是Bob拿的石子，正好是Bob的所有石子\n",
    "        ans = sum(totalValues[::2]) - sum(bobValues)\n",
    "        if ans > 0:\n",
    "            return 1\n",
    "        elif ans < 0:\n",
    "            return -1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        a = [aliceValues[i] + bobValues[i] for i in range(n)]\n",
    "        a.sort(reverse = True)\n",
    "        flag = (sum(aliceValues) - sum(bobValues)) + (sum(a[::2]) - sum(a[1::2]))\n",
    "        if flag > 0:\n",
    "            return 1\n",
    "        elif flag < 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        totalValues = [(a+b) for a,b in zip(aliceValues, bobValues)]\n",
    "        totalValues.sort(reverse=True)\n",
    "        # 所有Alice能拿到的石头的总价值，其中每个都多拿了Bob的对应石子,再减去本来就是Bob拿的石子，正好是Bob的所有石子\n",
    "        ans = sum(totalValues[::2]) - sum(bobValues)\n",
    "        if ans > 0:\n",
    "            return 1\n",
    "        elif ans < 0:\n",
    "            return -1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = sum(bobValues)\n",
    "        addValues = [aliceValues[i] + bobValues[i] for i in range(n)]\n",
    "        addValues.sort(reverse=True)\n",
    "        diff = sum(addValues[::2]) - total\n",
    "        ans = 0\n",
    "        if diff > 0:\n",
    "            ans = 1\n",
    "        if diff < 0:\n",
    "            ans = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = sum(bobValues)\n",
    "        addValues = [aliceValues[i] + bobValues[i] for i in range(n)]\n",
    "        addValues.sort(reverse=True)\n",
    "        diff = sum(addValues[::2]) - total\n",
    "        ans = 0\n",
    "        if diff > 0:\n",
    "            ans = 1\n",
    "        if diff < 0:\n",
    "            ans = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = sum(bobValues)\n",
    "        addValues = [aliceValues[i] + bobValues[i] for i in range(n)]\n",
    "        addValues.sort(reverse=True)\n",
    "        diff = sum(addValues[::2]) - total\n",
    "        ans = 0\n",
    "        if diff > 0:\n",
    "            ans = 1\n",
    "        if diff < 0:\n",
    "            ans = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = sum(bobValues)\n",
    "        addValues = [aliceValues[i] + bobValues[i] for i in range(n)]\n",
    "        addValues.sort(reverse=True)\n",
    "        diff = sum(addValues[::2]) - total\n",
    "        ans = 0\n",
    "        if diff > 0:\n",
    "            ans = 1\n",
    "        if diff < 0:\n",
    "            ans = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        totalValues = [(a+b) for a,b in zip(aliceValues, bobValues)]\n",
    "        totalValues.sort(reverse=True)\n",
    "        # 所有Alice能拿到的石头的总价值，其中每个都多拿了Bob的对应石子,再减去本来就是Bob拿的石子，正好是Bob的所有石子\n",
    "        ans = sum(totalValues[::2]) - sum(bobValues)\n",
    "        if ans > 0:\n",
    "            return 1\n",
    "        elif ans < 0:\n",
    "            return -1\n",
    "        return 0\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/stone-game-vi/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        a, b = aliceValues, bobValues\n",
    "        n = len(a)\n",
    "        total = sum(b)\n",
    "        a = [a[i] + b[i] for i in range(n)]\n",
    "        a.sort(reverse=True)\n",
    "        diff = sum(a[::2]) - total\n",
    "        ans = 0\n",
    "        if diff > 0:\n",
    "            ans = 1\n",
    "        if diff < 0:\n",
    "            ans = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        total_val = sorted([i+j for i, j in zip(aliceValues, bobValues)], reverse=True)\n",
    "        res = sum(total_val[::2]) - sum(bobValues)\n",
    "        if res > 0:\n",
    "            return 1 \n",
    "        elif res == 0:\n",
    "            return 0 \n",
    "        else:\n",
    "            return -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        # real_val = [i+j for i, j in zip(aliceValues, bobValues)]\n",
    "        # idx = sorted(zip(real_val, list(range(len(aliceValues)))), reverse=True)\n",
    "        # alice, bob = sum(aliceValues[i] for v, i in idx[::2]), sum(bobValues[i] for v, i in idx[1::2])\n",
    "        # if alice > bob:\n",
    "        #     return 1 \n",
    "        # elif alice == bob:\n",
    "        #     return 0 \n",
    "        # else:\n",
    "        #     return -1\n",
    "\n",
    "        # ---------------------------------------\n",
    "        total_val = sorted([i+j for i, j in zip(aliceValues, bobValues)], reverse=True)\n",
    "        res = sum(total_val[::2]) - sum(bobValues)\n",
    "        if res > 0:\n",
    "            return 1 \n",
    "        elif res == 0:\n",
    "            return 0 \n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\r\n",
    "        # 一个石子要么alice拿，要么bob拿 \r\n",
    "        # alice 可以拿 (n + 1) // 2 个石子 \r\n",
    "        # \r\n",
    "        n = len(aliceValues)\r\n",
    "        ids = [i for i in range(n)]\r\n",
    "        ids.sort(key=lambda i:aliceValues[i] + bobValues[i], reverse=True)\r\n",
    "       \r\n",
    "        \r\n",
    "        alice, bob = 0, 0\r\n",
    "        for i, idx in enumerate(ids):\r\n",
    "            if i % 2 == 0:\r\n",
    "                alice += aliceValues[idx] \r\n",
    "            else:\r\n",
    "                bob += bobValues[idx]\r\n",
    "        if alice > bob:\r\n",
    "            return 1 \r\n",
    "        elif alice == bob:\r\n",
    "            return 0 \r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        index = sorted(range(n), key = lambda x: aliceValues[x]+bobValues[x], reverse = True)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if i % 2: cnt -= bobValues[index[i]]\n",
    "            else:   cnt += aliceValues[index[i]]\n",
    "        if cnt > 0: return 1\n",
    "        elif cnt < 0:   return -1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        index = sorted(range(n), key = lambda x: aliceValues[x]+bobValues[x], reverse = True)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if i % 2: cnt -= bobValues[index[i]]\n",
    "            else:   cnt += aliceValues[index[i]]\n",
    "        if cnt > 0: return 1\n",
    "        elif cnt < 0:   return -1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        index = sorted(range(n), key = lambda x: aliceValues[x]+bobValues[x], reverse = True)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if i % 2: cnt -= bobValues[index[i]]\n",
    "            else:   cnt += aliceValues[index[i]]\n",
    "        if cnt > 0: return 1\n",
    "        elif cnt < 0:   return -1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = list(range(n))\n",
    "        total.sort(key = lambda i:aliceValues[i] + bobValues[i], reverse = True)\n",
    "        # print(total)\n",
    "        index = (n+1) << 1\n",
    "        x = sum((aliceValues[i] for i in total[::2]))\n",
    "        y = sum(bobValues[i] for i in total[1::2])\n",
    "        # print(x, y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        elif x > y:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = list(range(n))\n",
    "        total.sort(key = lambda i:aliceValues[i] + bobValues[i], reverse = True)\n",
    "        # print(total)\n",
    "        x = sum((aliceValues[i] for i in total[::2]))\n",
    "        y = sum(bobValues[i] for i in total[1::2])\n",
    "        # print(x, y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        elif x > y:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = list(range(n))\n",
    "        total.sort(key = lambda i:aliceValues[i] + bobValues[i], reverse = True)\n",
    "        # print(total)\n",
    "        x = sum((aliceValues[i] for i in total[::2]))\n",
    "        y = sum(bobValues[i] for i in total[1::2])\n",
    "        # print(x, y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        elif x > y:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        index = sorted(range(n), key = lambda x: aliceValues[x]+bobValues[x], reverse = True)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if i % 2: cnt -= bobValues[index[i]]\n",
    "            else:   cnt += aliceValues[index[i]]\n",
    "        if cnt > 0: return 1\n",
    "        elif cnt < 0:   return -1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = list(range(n))\n",
    "        total.sort(key = lambda i:aliceValues[i] + bobValues[i], reverse = True)\n",
    "        # print(total)\n",
    "        x = sum((aliceValues[i] for i in total[::2]))\n",
    "        y = sum(bobValues[i] for i in total[1::2])\n",
    "        # print(x, y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        elif x > y:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = list(range(n))\n",
    "        total.sort(key = lambda i:aliceValues[i] + bobValues[i], reverse = True)\n",
    "        # print(total)\n",
    "        x = sum((aliceValues[i] for i in total[::2]))\n",
    "        y = sum(bobValues[i] for i in total[1::2])\n",
    "        # print(x, y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        elif x > y:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = list(range(n))\n",
    "        total.sort(key = lambda i:aliceValues[i] + bobValues[i], reverse = True)\n",
    "        # print(total)\n",
    "        x = sum((aliceValues[i] for i in total[::2]))\n",
    "        y = sum(bobValues[i] for i in total[1::2])\n",
    "        # print(x, y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        elif x > y:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total = list(range(n))\n",
    "        total.sort(key = lambda i:aliceValues[i] + bobValues[i], reverse = True)\n",
    "        # print(total)\n",
    "        x = sum((aliceValues[i] for i in total[::2]))\n",
    "        y = sum(bobValues[i] for i in total[1::2])\n",
    "        # print(x, y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        elif x > y:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        p = sorted(list(range(len(aliceValues))), key = lambda i:aliceValues[i]+bobValues[i], reverse=True)\n",
    "        a = sum(aliceValues[i] for i in p[::2])\n",
    "        b = sum(bobValues[i] for i in p[1::2])\n",
    "        return 1 if a > b else 0 if a == b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        arr = [(x + y, x) for x, y in zip(aliceValues, bobValues)]\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        alice_sum = bob_sum = 0\n",
    "        flag = True\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if flag:\n",
    "                alice_sum += arr[i][1]\n",
    "            else:\n",
    "                bob_sum += (arr[i][0] - arr[i][1])\n",
    "            flag = not flag\n",
    "        if alice_sum > bob_sum:\n",
    "            return 1\n",
    "        elif alice_sum == bob_sum:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        stones = [(aliceValues[i] + bobValues[i],aliceValues[i],bobValues[i]) for i in range(n)]\n",
    "        stones.sort(reverse = True)\n",
    "\n",
    "        alice = 0\n",
    "        bob = 0\n",
    "\n",
    "        for i,t in enumerate(stones):\n",
    "            if i%2 == 0:\n",
    "                alice += t[1]\n",
    "            else:\n",
    "                bob += t[2]\n",
    "            \n",
    "        if alice == bob:\n",
    "            return 0\n",
    "        elif alice > bob:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        total_values = [(aliceValues[i] + bobValues[i], aliceValues[i], bobValues[i]) for i in range(n)]\n",
    "        \n",
    "        # 按照石头对两人总价值的贡献进行排序\n",
    "        total_values.sort(reverse=True)\n",
    "        \n",
    "        alice_score, bob_score = 0, 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:  # Alice's turn\n",
    "                alice_score += total_values[i][1]\n",
    "            else:  # Bob's turn\n",
    "                bob_score += total_values[i][2]\n",
    "                \n",
    "        if alice_score > bob_score:\n",
    "            return 1\n",
    "        elif alice_score < bob_score:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "\n",
    "        # 按两人总分排序石子\n",
    "        lst = [(aliceValues[i], bobValues[i]) for i in range(n)]\n",
    "        lst.sort(key=lambda x: x[0] + x[1], reverse=True)\n",
    "\n",
    "        alice, bob = 0, 0\n",
    "        for i in range(len(lst)):\n",
    "            if i % 2 == 0:\n",
    "                alice += lst[i][0]\n",
    "            else:\n",
    "                bob += lst[i][1]\n",
    "\n",
    "        if alice > bob:\n",
    "            return 1\n",
    "        elif alice < bob:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        # 排序，两种价值加起来越大的，越靠前\n",
    "        n = len(aliceValues)\n",
    "        rec = [(aliceValues[i], bobValues[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:(x[0]+x[1]), reverse=True)\n",
    "        first,second = 0,0\n",
    "        for i in range(n):\n",
    "            if i%2==0:\n",
    "                first += rec[i][0]\n",
    "            else:\n",
    "                second += rec[i][1]\n",
    "        if first==second:\n",
    "            return 0\n",
    "        elif first>second:\n",
    "            return 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        values = sorted(((i, j) for i,j in zip(aliceValues, bobValues)), key = sum, reverse = True)\n",
    "        a = 0\n",
    "        b = 0\n",
    "        for i in range(len(values)):\n",
    "            if i&1:\n",
    "                b += values[i][1]\n",
    "            else:\n",
    "                a += values[i][0]\n",
    "        if a > b:\n",
    "            return 1\n",
    "        elif a == b:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        a = sorted(zip(aliceValues, bobValues), key=lambda t: t[0] + t[1], reverse=True)\n",
    "        f = lambda i: sum(a[t][i] for t in range(i, len(a), 2))\n",
    "        a = f(0) - f(1)\n",
    "        return a and (1 if a > 0 else -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        rec = [(aliceValues[i], bobValues[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:(x[0]+x[1]), reverse=True)\n",
    "        first = sum([rec[i][0] for i in range(n) if i%2==0])\n",
    "        secend = sum([rec[i][1] for i in range(n) if i%2!=0])\n",
    "        if first==secend:\n",
    "            return 0\n",
    "        elif first>secend:\n",
    "            return 1\n",
    "        return -1\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        values = [(aliceValues[i] ,bobValues[i]) for i in range(len(aliceValues))]\n",
    "        n = len(aliceValues)\n",
    "        used = [False] * n\n",
    "        values.sort(key=lambda x:(x[0]+x[1]), reverse=True)\n",
    "        A, B = 0, 0\n",
    "        for i in range(n):\n",
    "            if not i % 2 :\n",
    "                A += values[i][0]\n",
    "            else:\n",
    "                B += values[i][1]\n",
    "        if A > B: \n",
    "            return 1\n",
    "        elif A < B:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0               \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        values = [(aliceValues[i] + bobValues[i], i) for i in range(len(aliceValues))]\n",
    "        values.sort(reverse=True)\n",
    "        alice = 0\n",
    "        bob = 0\n",
    "        cur = 0\n",
    "        for val, i in values:\n",
    "            if cur % 2 == 0:\n",
    "                alice += aliceValues[i]\n",
    "            else:\n",
    "                bob += bobValues[i]\n",
    "            cur += 1\n",
    "        if alice > bob:\n",
    "            return 1\n",
    "        elif alice == bob:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        q = []\n",
    "        n = len(aliceValues)\n",
    "        for i in range(n):\n",
    "            q.append((aliceValues[i] + bobValues[i], i))\n",
    "        q.sort(reverse=True)\n",
    "        cur = 0\n",
    "        a = b = 0\n",
    "        while cur < n:\n",
    "            if cur % 2 == 0:\n",
    "                a += aliceValues[q[cur][1]]\n",
    "            else:\n",
    "                b += bobValues[q[cur][1]]\n",
    "            cur += 1\n",
    "        return 1 if a > b else -1 if a < b else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        s = [[a + b, a, b] for a, b in zip(aliceValues, bobValues)]\n",
    "        s.sort(reverse=True)\n",
    "        s1, s2 = sum(x[1] for x in s[::2]), sum(x[2] for x in s[1::2])\n",
    "        if s1 > s2:\n",
    "            return 1\n",
    "        elif s1 == s2:\n",
    "            return 0\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int: \n",
    "        n = len(aliceValues)\n",
    "        stones = [(aliceValues[i] + bobValues[i], i) for i in range(n)]\n",
    "        stones.sort(reverse=True)\n",
    "        a_score, b_score = 0, 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                a_score += aliceValues[stones[i][1]]\n",
    "            else:\n",
    "                b_score += bobValues[stones[i][1]]\n",
    "        if a_score > b_score:\n",
    "            return 1\n",
    "        elif a_score < b_score:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)           \n",
    "        sums = [(aliceValues[i] + bobValues[i], i) for i in range(n)]\n",
    "        sums.sort(reverse = True)\n",
    "        sums_alice, sums_bob = 0, 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                sums_alice += aliceValues[sums[i][-1]]\n",
    "            else:\n",
    "                sums_bob += bobValues[sums[i][-1]]\n",
    "        ret = 1\n",
    "        if sums_bob == sums_alice:\n",
    "            ret = 0\n",
    "        elif sums_bob > sums_alice:\n",
    "            ret = -1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\r\n",
    "        # 一个石子要么alice拿，要么bob拿 \r\n",
    "        # 所以 贡献为 aliceValues[i] - bobValues[i]\r\n",
    "        # alice 可以拿 (n + 1) // 2 个石子 \r\n",
    "        # \r\n",
    "        n = len(aliceValues)\r\n",
    "        v = [(x + y, i) for i, (x, y) in enumerate(zip(aliceValues, bobValues))]\r\n",
    "        v.sort(reverse=True)\r\n",
    "        \r\n",
    "        alice, bob = 0, 0\r\n",
    "        for i in range(n):\r\n",
    "            if i % 2 == 0:\r\n",
    "                alice += aliceValues[v[i][1]] \r\n",
    "            else:\r\n",
    "                bob += bobValues[v[i][1]]\r\n",
    "        if alice > bob:\r\n",
    "            return 1 \r\n",
    "        elif alice == bob:\r\n",
    "            return 0 \r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        arr = [None] * n\n",
    "        alice = bob = 0\n",
    "        for i in range(n):\n",
    "            arr[i] = (aliceValues[i] + bobValues[i], aliceValues[i], bobValues[i])\n",
    "        arr.sort(key = lambda x: (-x[0]))\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                alice += arr[i][1]\n",
    "            else:\n",
    "                bob += arr[i][2]\n",
    "        if bob == alice: return 0\n",
    "        return 1 if alice > bob else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        t = sorted(zip(aliceValues, bobValues), key = lambda x: -x[0]-x[1])\n",
    "        d = 0\n",
    "        for i in range(len(t)):\n",
    "            if ~i & 1: d += t[i][0]\n",
    "            else: d -= t[i][1]\n",
    "        if d == 0: return 0\n",
    "        return 1 if d > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "将两组石头的价值合并，每次取价值最大的那一组\n",
    "'''\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        n = len(aliceValues)\n",
    "        newValues = [a+b for a, b in zip(aliceValues, bobValues)]\n",
    "        newValues = [(i, x) for i, x in enumerate(newValues)]\n",
    "        newValues.sort(key=lambda x: x[1], reverse=True)\n",
    "        s1, s2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                # 偶数下标alice来取\n",
    "                s1 += aliceValues[newValues[i][0]]\n",
    "            else:\n",
    "                # 奇数下标bob来取\n",
    "                s2 += bobValues[newValues[i][0]]\n",
    "        \n",
    "        if s1 > s2: return 1\n",
    "        elif s1 == s2: return 0\n",
    "        else: return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        values = [x + y for x, y in zip(aliceValues,bobValues)]\n",
    "        Index = [i[0] for i in sorted(enumerate(values), key=lambda x:x[1],reverse=True)]\n",
    "        aliWin = 0\n",
    "        for i in Index[::2]:\n",
    "            aliWin += aliceValues[i]\n",
    "        for i in Index[1::2]:\n",
    "            aliWin -= bobValues[i]\n",
    "\n",
    "        if aliWin>0:\n",
    "            return 1\n",
    "        elif aliWin<0:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        real_val = [i+j for i, j in zip(aliceValues, bobValues)]\n",
    "        idx = sorted(zip(real_val, list(range(len(aliceValues)))), reverse=True)\n",
    "        alice, bob = sum(aliceValues[i] for v, i in idx[::2]), sum(bobValues[i] for v, i in idx[1::2])\n",
    "        if alice > bob:\n",
    "            return 1 \n",
    "        elif alice == bob:\n",
    "            return 0 \n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i in range(len(aliceValues)):\n",
    "            dic[i]+=aliceValues[i]+bobValues[i]\n",
    "        tmp = sorted(dic)\n",
    "        tmp.sort(key = lambda x:dic[x],reverse=True)\n",
    "        res = 0\n",
    "        for i in range(len(tmp)):\n",
    "            if i%2==0:\n",
    "                res+=aliceValues[tmp[i]]\n",
    "            else:\n",
    "                res-=bobValues[tmp[i]]\n",
    "        if res>0:\n",
    "            return 1\n",
    "        elif res==0:\n",
    "            return 0\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i in range(len(aliceValues)):\n",
    "            dic[i]+=aliceValues[i]+bobValues[i]\n",
    "        tmp = sorted(dic)\n",
    "        tmp.sort(key = lambda x:dic[x],reverse=True)\n",
    "        res = 0\n",
    "        for i in range(len(tmp)):\n",
    "            if i%2==0:\n",
    "                res+=aliceValues[tmp[i]]\n",
    "            else:\n",
    "                res-=bobValues[tmp[i]]\n",
    "        if res>0:\n",
    "            return 1\n",
    "        elif res==0:\n",
    "            return 0\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i in range(len(aliceValues)):\n",
    "            dic[i]+=aliceValues[i]+bobValues[i]\n",
    "        tmp = sorted(dic)\n",
    "        tmp.sort(key = lambda x:dic[x],reverse=True)\n",
    "        res = 0\n",
    "        for i in range(len(tmp)):\n",
    "            if i%2==0:\n",
    "                res+=aliceValues[tmp[i]]\n",
    "            else:\n",
    "                res-=bobValues[tmp[i]]\n",
    "        if res>0:\n",
    "            return 1\n",
    "        elif res==0:\n",
    "            return 0\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i in range(len(aliceValues)):\n",
    "            dic[i]+=aliceValues[i]+bobValues[i]\n",
    "        tmp = sorted(dic)\n",
    "        tmp.sort(key = lambda x:dic[x],reverse=True)\n",
    "        res = 0\n",
    "        for i in range(len(tmp)):\n",
    "            if i%2==0:\n",
    "                res+=aliceValues[tmp[i]]\n",
    "            else:\n",
    "                res-=bobValues[tmp[i]]\n",
    "        if res>0:\n",
    "            return 1\n",
    "        elif res==0:\n",
    "            return 0\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        tmp = []\n",
    "        for i in range(len(aliceValues)):\n",
    "            t = aliceValues[i] + bobValues[i]\n",
    "            tmp.append([i,t])\n",
    "        tmp.sort(key=lambda x : x[1],reverse=True)\n",
    "        a,b = 0,0\n",
    "        for i in range(len(tmp)):\n",
    "            if i%2==0:\n",
    "                a += aliceValues[tmp[i][0]]\n",
    "            else:\n",
    "                b += bobValues[tmp[i][0]]\n",
    "        if a>b:\n",
    "            return 1\n",
    "        elif a<b:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        sum = []\n",
    "        for i, (a,b) in enumerate(zip(aliceValues, bobValues)):\n",
    "            sum.append([i, a+b])\n",
    "        sum.sort(key=lambda x: x[1], reverse=True)\n",
    "        flag, valA, valB = True, 0, 0\n",
    "        for x in sum:\n",
    "            if flag:\n",
    "                valA += aliceValues[x[0]]\n",
    "            else:\n",
    "                valB += bobValues[x[0]]\n",
    "            flag = not flag\n",
    "        return 1 if valA > valB else (0 if valA == valB else -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        data = [[aliceValues[i] + bobValues[i], i] for i in range(len(aliceValues))]\n",
    "        data.sort(key=lambda x: x[0], reverse=True)\n",
    "        a = sum(aliceValues[data[i][1]] for i in range(0, len(data), 2))\n",
    "        b = sum(bobValues[data[i][1]] for i in range(1, len(data), 2))\n",
    "        return 0 if a == b else (1 if a > b else -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        data = [[aliceValues[i] + bobValues[i], i] for i in range(len(aliceValues))]\n",
    "        data.sort(key=lambda x: x[0], reverse=True)\n",
    "        a = sum(aliceValues[data[i][1]] for i in range(0, len(data), 2))\n",
    "        b = sum(bobValues[data[i][1]] for i in range(1, len(data), 2))\n",
    "        return 0 if a == b else (1 if a > b else -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        data = [[aliceValues[i] + bobValues[i], i] for i in range(len(aliceValues))]\n",
    "        data.sort(key=lambda x: x[0], reverse=True)\n",
    "        a = sum(aliceValues[data[i][1]] for i in range(0, len(data), 2))\n",
    "        b = sum(bobValues[data[i][1]] for i in range(1, len(data), 2))\n",
    "        return 0 if a == b else (1 if a > b else -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        data = [[aliceValues[i] + bobValues[i], i] for i in range(len(aliceValues))]\n",
    "        data.sort(key=lambda x: x[0], reverse=True)\n",
    "        a = sum(aliceValues[data[i][1]] for i in range(0, len(data), 2))\n",
    "        b = sum(bobValues[data[i][1]] for i in range(1, len(data), 2))\n",
    "        return 0 if a == b else (1 if a > b else -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        value = []\n",
    "        for i in range(len(aliceValues)):\n",
    "            value.append([aliceValues[i]+bobValues[i],i])\n",
    "        value.sort(key=lambda x: x[0],reverse=True)\n",
    "        # print(value)\n",
    "        scoreA = 0\n",
    "        scoreB = 0\n",
    "        for i in range(len(aliceValues)):\n",
    "            if i%2 == 0:\n",
    "                scoreA += aliceValues[value[i][1]]\n",
    "            else:\n",
    "                scoreB += bobValues[value[i][1]]\n",
    "        if scoreA > scoreB:\n",
    "            return 1\n",
    "        elif scoreA < scoreB:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        data = [[aliceValues[i] + bobValues[i], i] for i in range(len(aliceValues))]\n",
    "        data.sort(key=lambda x: x[0], reverse=True)\n",
    "        a = sum(aliceValues[data[i][1]] for i in range(0, len(data), 2))\n",
    "        b = sum(bobValues[data[i][1]] for i in range(1, len(data), 2))\n",
    "        return 0 if a == b else (1 if a > b else -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        arr = []\n",
    "        for i, (a, b) in enumerate(zip(aliceValues, bobValues)):\n",
    "            arr.append((a + b, i))\n",
    "        arr.sort(reverse = True)\n",
    "        print(arr)\n",
    "        ans = 0\n",
    "        for i, (x, p) in enumerate(arr):\n",
    "            if i & 1:\n",
    "                ans -= bobValues[p]\n",
    "            else:\n",
    "                ans += aliceValues[p]\n",
    "        if ans > 0: return 1\n",
    "        if ans < 0: return -1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        v = [(a+b, i) for a,b,i in zip(aliceValues, bobValues,range(len(aliceValues)))]\n",
    "        v.sort(key=lambda x:-x[0])\n",
    "        aval = bval = 0\n",
    "        for i in range(0, len(aliceValues), 2):\n",
    "            aval += aliceValues[v[i][1]]\n",
    "        for i in range(1, len(aliceValues), 2):\n",
    "            bval += bobValues[v[i][1]]\n",
    "        if aval > bval:\n",
    "            return 1\n",
    "        elif aval < bval:\n",
    "            return -1\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        s=[(aliceValues[i]+bobValues[i],i) for i in range(len(aliceValues))]\n",
    "        s=sorted(s,key=lambda x:-x[0])\n",
    "        s1=s[0::2]\n",
    "        s2=s[1::2]\n",
    "        A=B=0\n",
    "        for x in s1:\n",
    "            A+=aliceValues[x[1]]\n",
    "        for x in s2:\n",
    "            B+=bobValues[x[1]]\n",
    "        if A>B:\n",
    "            return 1\n",
    "        elif A==B:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        s=[(aliceValues[i]+bobValues[i],i) for i in range(len(aliceValues))]\n",
    "        s=sorted(s,key=lambda x:-x[0])\n",
    "        s1=s[0::2]\n",
    "        s2=s[1::2]\n",
    "        A=B=0\n",
    "        for x in s1:\n",
    "            A+=aliceValues[x[1]]\n",
    "        for x in s2:\n",
    "            B+=bobValues[x[1]]\n",
    "        if A>B:\n",
    "            return 1\n",
    "        elif A==B:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        # 选择当前石子差值最大的（负数最大）或者整数最大\n",
    "\n",
    "        diff_alice = []\n",
    "        n = len(aliceValues)\n",
    "        for i in range(n):\n",
    "            diff_alice.append(abs(aliceValues[i]+bobValues[i]))\n",
    "        \n",
    "        used_lst = [False] * n\n",
    "        \n",
    "        diff_alice = [(i, item) for i, item in enumerate(diff_alice)]\n",
    "        diff_alice = sorted(diff_alice, key=lambda x: -x[1])\n",
    "\n",
    "        print(diff_alice)\n",
    "        aliceVal, bobVal = 0, 0\n",
    "        for idx, info in enumerate(diff_alice):\n",
    "            i, diff = info\n",
    "            if idx & 1 == 0:\n",
    "                # alice\n",
    "                aliceVal += aliceValues[i]\n",
    "            else:\n",
    "                # bob\n",
    "                bobVal += bobValues[i]\n",
    "\n",
    "        if aliceVal > bobVal:\n",
    "            return 1\n",
    "        elif aliceVal == bobVal:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        # 选择当前石子差值最大的（负数最大）或者整数最大\n",
    "\n",
    "        diff_alice = []\n",
    "        n = len(aliceValues)\n",
    "        for i in range(n):\n",
    "            diff_alice.append(abs(aliceValues[i]+bobValues[i]))\n",
    "        \n",
    "        used_lst = [False] * n\n",
    "        \n",
    "        diff_alice = [(i, item) for i, item in enumerate(diff_alice)]\n",
    "        diff_alice = sorted(diff_alice, key=lambda x: -x[1])\n",
    "\n",
    "        print(diff_alice)\n",
    "        aliceVal, bobVal = 0, 0\n",
    "        for idx, info in enumerate(diff_alice):\n",
    "            i, diff = info\n",
    "            if idx & 1 == 0:\n",
    "                # alice\n",
    "                aliceVal += aliceValues[i]\n",
    "            else:\n",
    "                # bob\n",
    "                bobVal += bobValues[i]\n",
    "\n",
    "        if aliceVal > bobVal:\n",
    "            return 1\n",
    "        elif aliceVal == bobVal:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:\n",
    "        # 选择当前石子差值最大的（负数最大）或者整数最大\n",
    "\n",
    "        diff_alice = []\n",
    "        n = len(aliceValues)\n",
    "        for i in range(n):\n",
    "            diff_alice.append(abs(aliceValues[i]+bobValues[i]))\n",
    "        \n",
    "        used_lst = [False] * n\n",
    "        \n",
    "        diff_alice = [(i, item) for i, item in enumerate(diff_alice)]\n",
    "        diff_alice = sorted(diff_alice, key=lambda x: -x[1])\n",
    "\n",
    "        print(diff_alice)\n",
    "        aliceVal, bobVal = 0, 0\n",
    "        for idx, info in enumerate(diff_alice):\n",
    "            i, diff = info\n",
    "            if idx & 1 == 0:\n",
    "                # alice\n",
    "                aliceVal += aliceValues[i]\n",
    "            else:\n",
    "                # bob\n",
    "                bobVal += bobValues[i]\n",
    "\n",
    "        if aliceVal > bobVal:\n",
    "            return 1\n",
    "        elif aliceVal == bobVal:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
